# source: https://leetcode.cn/problems/partition-array-for-maximum-sum/ 划分DP 记忆化搜索
from functools import cache
from itertools import accumulate


class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        @cache
        def dfs(i):
            if i < 0:
                return 0    
            mx = arr[i]
            res = -1
            for ind in range(i, max(i-k, -1), -1):
                mx = max(mx, arr[ind])
                res = max(dfs(ind-1) + mx * (i - ind + 1), res)
            return res
        return dfs(len(arr)-1)


# source: https://leetcode.cn/problems/split-array-largest-sum/ 划分DP 记忆化搜索

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        prefix_sum = [0] + list(accumulate(nums))  # 前缀和计算
        @cache
        def dfs(i, cnt):
            if cnt == 1:
                return prefix_sum[i + 1]  # 剩下的所有数作为最后一部分
            res = float('inf')
            # 从 `j` 开始新的分割
            for j in range(i):
                res = min(res, max(dfs(j, cnt - 1), prefix_sum[i + 1] - prefix_sum[j + 1]))
            return res

        return dfs(len(nums) - 1, m)

# source: https://leetcode.cn/problems/minimum-white-tiles-after-covering-with-carpets/description/ 划分DP 记忆化搜索
from functools import cache

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        @cache
        def dfs(i, j):
            if i < 0:  # 边界条件
                return 0
            if j == 0:  # 没有地毯可用时，统计剩余的 '1'
                return sum(1 for x in floor[:i + 1] if x == '1')

            # 不覆盖当前 `i`
            res2 = dfs(i - 1, j) + int(floor[i])

            # 尝试覆盖 `i` 到 `max(i-carpetLen+1, 0)`
            res1 = dfs(i - carpetLen, j - 1)

            return min(res1, res2)  # 取最优方案（剩余 `1` 最少）

        return dfs(len(floor) - 1, numCarpets)
